package Tree;

public class _235_LowestCommonAncestorofaBinarySearchTree {
    public TreeNode lowestCommonAncestor_1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root==q || root==p) return root;
        TreeNode lnode = lowestCommonAncestor_1(root.left, p, q);
        TreeNode rnode = lowestCommonAncestor_1(root.right, p, q);
        if (lnode != null && rnode != null) {
            return root;
        } else {
            return lnode != null ? lnode : rnode;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return root;
        int high = Math.max(p.val, q.val);
        int low = Math.min(p.val, q.val);
        if (low <= root.val && root.val <= high) {
            return root;
        } else {
            return low > root.val ? lowestCommonAncestor(root.right, p, q) : lowestCommonAncestor(root.left, p, q);
        }
    }
}
